Umar ibn Abd al-Aziz asked Abu Bakr ibn Sulayman ibn Abi Hathamah what was the reason that it used to be written, ''"From the Khalifah of the Messenger of Allah, may Allah bless him and grant him peace,"'' in the time of Abu Bakr, then later Umar used to write at first, ''"From the Khalifah of Abu Bakr."''? Then who was the first to write, ''"From the Amir al-Muminin (the Commander of the Believers)"''?
He said, ''"Ash-Shifa, who was one of the women of the Muhajirun, told me that Abu Bakr used to write, ''"From the Khalifah of the Messenger of Allah"'', and Umar used to write, ''"From the Khalifah of the Khalifah of the Messenger of Allah,"'' until one day Umar wrote to the governor of Iraq, to send him two strong men whom he could ask about Iraq and its inhabitants. He sent to him Labid ibn Rabi'ah and Adi ibn Hatim, and they came to Madinah and entered the mosque where they found Amr ibn al-'As.
They said, ''"Get permission for us (to visit) the Amir al-Muminin."'' Amr said, ''"You two, by Allah, have hit upon his name!"'' Then Amr went in to him and said, ''"Peace be upon you, Amir al-Mu'minin."'' He said, ''"What occurred to you about this name? You must explain what you have said."'' He told him and said, ''"You are the amir (commander) and we are the muminun (the believers)."'' Thus letters have continued to be written with that from that day.
An-Nawawi said in his Tahdhib: Adi ibn Hatim and Labid ibn Rabi'ah named him thus when they came as a deputation from 'Iraq. It has been said that al-Mughirah ibn Shu'bah named him with this name. It has also been said that 'Umar said to people, 'You are the believers and I am your amir,' and so he was called Amir al-Muminin, and before that he was known as the Khalifah of the Khalifah of the Messenger of Allah, but they changed from that expression because of its length.
Mu'awiyyah ibn Qurrah said: It used to be written 'From Abu Bakr the Khalifah of the Messenger of Allah,' and then when it was 'Umar ibn al-Khattab they wanted to say, 'The Khalifah of the Khalifah of the Messenger of Allah.' 'Umar said, 'This is lengthy.' They said, 'No. But we have appointed you as amir over us, so you are our amir.' He said, 'Yes, and you are the believers, and I am your amir.' Then it became written Amir al-Muminin.〔History of the Caliphs by Suyuti〕